home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-01 / cuj1008.zip / RAMEY.ZIP / SUBLIST.C < prev    next >
C/C++ Source or Header  |  1991-10-14  |  11KB  |  414 lines
  1. /*
  2. Postman's Sort (R) Version 1.0
  3. Copyright (c) Robert Ramey 1991. All Rights Reserved
  4. */
  5.  
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <assert.h>
  9. #include <links.h>
  10. #include "psort.h"
  11. #include "sublist.h"
  12. #include "io.h"
  13. #include "os.h"
  14. #include "arg.h"
  15.  
  16. FILE *wfinptr = (FILE *)NULL;    /* work file pointer for input*/
  17. char *wfinbuf = NULL;            /* and buffer for input */
  18. int rb_size = RB_SIZE;
  19.  
  20. FILE *wfoutptr = (FILE *)NULL;    /* work file pointer for output */
  21. char *wfoutbuf = NULL;            /* and buffer output */
  22. int sb_size = SB_SIZE;
  23.  
  24. char wfname[DIR_NAME_SIZE + 9] = "";    /* name of work file */
  25. FILE_SIZE next_disk;
  26.  
  27. STACK *s_stack;
  28.  
  29. private void
  30. sublist_windup(void);
  31. private void
  32. sublist_write(int, SUBLIST *);
  33. private RECORD *
  34. sublist_read(SUBLIST *);
  35. void *
  36. get_space(STACK *, size_t);
  37. void *
  38. need(STACK *, size_t);
  39. /*********************************************************************
  40. sublist_init - get command line args associated with sublists
  41. **********************************************************************/
  42. void
  43. sublist_init(argc, argv)
  44. unsigned int argc;
  45. char *argv[];
  46. {
  47.     unsigned int i, l;
  48.     char *cptr;
  49.  
  50.     rec_init(argc, argv);
  51.  
  52.     /* default temporary directory */
  53.     cptr = getenv("TMP");
  54.     if(cptr != (char *)NULL){
  55.         strcpy(wfname, cptr);
  56.         strcat(wfname, FNDELIM);
  57.     }
  58.  
  59.     i = arg_find(argc, argv, "-t");
  60.     if(i == -1)
  61.         i = arg_find(argc, argv, "-T");
  62.     if(i != -1){
  63.         argv[i++] = "";
  64.         if(i == argc
  65.         || *argv[i] == '-'
  66.         || *argv[i] == '\0'){
  67.             strcpy(wfname, "");
  68.         }
  69.         else{
  70.             /* save new name root for work file */
  71.             if(strlen(argv[i]) + 9 > DIR_NAME_SIZE)
  72.                 error("Temporary directory name too long");
  73.             strcpy(wfname, argv[i]);
  74.             strcat(wfname, FNDELIM);
  75.             argv[i] = "";
  76.         }
  77.     }
  78.     i = arg_find(argc, argv, "-sb");
  79.     if(i != -1){
  80.         argv[i++] = "";
  81.         if(i >= argc
  82.         || *argv[i] == '-'
  83.         || *argv[i] == '0')
  84.             error("-sb switch must specify block size in K");
  85.         arg_value(argv[i], &sb_size);
  86.         if(sb_size > MAX_BUFFER_SIZE)
  87.             sb_size = MAX_BUFFER_SIZE;
  88.         argv[i] = "";
  89.     }
  90.     i = arg_find(argc, argv, "-rb");
  91.     if(i != -1){
  92.         argv[i++] = "";
  93.         if(i >= argc
  94.         || *argv[i] == '-'
  95.         || *argv[i] == '0')
  96.             error("-rb switch must specify block size in K");
  97.         arg_value(argv[i], &rb_size);
  98.         if(rb_size > MAX_BUFFER_SIZE)
  99.             rb_size = MAX_BUFFER_SIZE;
  100.         argv[i] = "";
  101.     }
  102.  
  103.     /* setup for work file names */
  104.     strcat(wfname, "SXXXXXXX");
  105.     mktemp(wfname);
  106.     next_disk = 0L;
  107.  
  108.     /* reserve memory for work file buffer before someone */
  109.     /* else takes it */
  110.     if(rb_size>0){
  111.         wfinbuf = malloc(rb_size * K);
  112.         if(!wfinbuf)
  113.             error("Couldn't get memory for workfile input buffer");
  114.     }
  115.     if(sb_size>0){
  116.         wfoutbuf = malloc(sb_size * K);
  117.         if(!wfoutbuf)
  118.             error("Couldn't get memory for workfile output buffer");
  119.     }
  120.  
  121.     if(atexit(sublist_windup))
  122.         error("Couldn't register sublist_windup");
  123.  
  124.     s_stack = stk_alloc();
  125.  
  126.     return;
  127. }
  128. /*********************************************************************
  129. sublist_allocate - get an array of sublists of the specified size.
  130. If necessary write out other sublists to disk to make room in
  131. main memory.
  132. **********************************************************************/
  133. SUBLIST *
  134. sublist_allocate(n)
  135. unsigned int n;        /* number of sublists to be allocated */
  136. {
  137.     register SUBLIST *sptr;
  138.     int i;
  139.  
  140.     assert(stk_push(s_stack));
  141.     sptr = (SUBLIST *)get_space(s_stack, n * (SEG_SIZE)sizeof(SUBLIST));
  142.  
  143.     /* initialize sublists_array */
  144.     sptr += n;
  145.     for(i = n; i--;){
  146.         --sptr;
  147.         sptr->size =
  148.         sptr->pcount =
  149.         sptr->count = 0;
  150.         sptr->disk = EOF;
  151.         sptr->memory = (RECORD *)NULL;
  152.     }
  153.     return sptr;
  154. }
  155. /*********************************************************************
  156. sublist_fclose - close swap files.
  157. **********************************************************************/
  158. void
  159. sublist_fclose(){
  160.  
  161.     /* stack state of output file */
  162.     *(FILE_SIZE *)get_space(s_stack, sizeof(FILE_SIZE)) = next_disk;
  163.  
  164.     /* if output has overflowed to stack */
  165.     if(wfoutptr){
  166.         fflush(wfoutptr);    /* make sure all the data can be read */
  167.         if(!wfinptr){
  168.             wfinptr = fdopen(fileno(wfoutptr), "rb");
  169.             if(!wfinptr)
  170.                 error("Couldn't open working file for reading");
  171.             if(rb_size != 0)
  172.                 assert(!setvbuf(wfinptr, wfinbuf, _IOFBF, rb_size));
  173.         }
  174.         clearerr(wfinptr);
  175.     }
  176.     return;
  177. }
  178. /*********************************************************************
  179. sublist_free - restore sublist stack to its state before last
  180. allocate
  181. **********************************************************************/
  182. void
  183. sublist_free(){
  184.  
  185.     /* recover original state of output file */
  186.     next_disk = *((FILE_SIZE *)stk_end(s_stack) - 1);
  187.  
  188.     /* throw away sublists */
  189.     assert(stk_pop(s_stack));
  190.     return;
  191. }
  192. /*********************************************************************
  193. sublist_shrink - eliminate array of sublist headers from stack.
  194. otherwise leave state of stack the same.
  195. **********************************************************************/
  196. void
  197. sublist_shrink()
  198. {
  199.     FILE_SIZE next_disk;
  200.  
  201.     next_disk = *((FILE_SIZE *)stk_end(s_stack) - 1);
  202.     assert(stk_pop(s_stack));
  203.     assert(stk_push(s_stack));
  204.     *(FILE_SIZE *)get_space(s_stack, sizeof(FILE_SIZE)) = next_disk;
  205.     return;
  206. }
  207. /*********************************************************************
  208. sublist_empty - write all sublists to disk upto amount to be emptied
  209. **********************************************************************/
  210. void
  211. sublist_empty(blk_num, sublist, sublist_count)
  212. int blk_num, sublist_count;
  213. SUBLIST *sublist;
  214. {
  215.     int j;
  216.     FILE_SIZE save_disk;
  217.  
  218.     if(!wfoutptr){
  219.         wfoutptr = fopen(wfname, "w+b");
  220.         if(!wfoutptr)
  221.             error("Couldn't open work file for output");
  222.         if(sb_size != 0)
  223.             assert(!setvbuf(wfoutptr, wfoutbuf, _IOFBF, sb_size*K));
  224.     }
  225.     /*
  226.     save_disk = ftell(wfoutptr);
  227.     */
  228.     assert(!fseek(wfoutptr, next_disk, SEEK_SET));
  229.  
  230.     /* write sublists */
  231.     for(j = sublist_count; j-- > 0;)
  232.         sublist_write(blk_num, sublist + j);
  233.  
  234.     next_disk = ftell(wfoutptr);
  235.     /*
  236.     assert(!fseek(wfoutptr, save_disk, SEEK_SET));
  237.     */
  238.     return ;
  239. }
  240. /*********************************************************************
  241. sublist_write - empty a sublist to disk as long as the block number
  242. in the record is greater than or equal to the one specified
  243. **********************************************************************/
  244. private
  245. void
  246. sublist_write(blk_num, sublist)
  247. int blk_num;
  248. SUBLIST *sublist;
  249. {
  250.     RECORD *record_address, *next_address;
  251.     size_t record_size;
  252.     FILE_SIZE file_address;
  253.     unsigned int i;
  254.  
  255.     next_address = sublist->memory;
  256.     if(next_address == (RECORD *)NULL
  257.     || blk_num > rec_frame(next_address))
  258.         return;
  259.  
  260.     /* get disk address */
  261.     file_address = ftell(wfoutptr);
  262.  
  263.     /* write link to previous record in this sublist */
  264.     efwrite(&(sublist->disk), sizeof(FILE_SIZE), 1, wfoutptr);
  265.  
  266.     /* set up new disk pointer in sublist */
  267.     sublist->disk = file_address;
  268.  
  269.     /* write all records in sublist to disk */
  270.     i = 0;
  271.     for(;;){
  272.         /* move to next member of chain */
  273.         record_address = next_address;
  274.         record_size = rec_size(record_address) + 1;
  275.         sublist->size += record_size + sizeof(ADDRESS);
  276.         ++i;
  277.  
  278.         /* check to see if this is the last record */
  279.         next_address = (RECORD *)nxtelem((ADDRESS)record_address, 0);
  280.         if(next_address == (RECORD *)NULL
  281.         || blk_num > rec_frame(next_address)){
  282.             /* if it is mark it with a 1 */
  283.             rec_eob(record_address) = 1;
  284.             efwrite((void *)record_address, record_size, 1, wfoutptr);
  285.             break;
  286.         }
  287.         else{
  288.             rec_eob(record_address) = 0;
  289.             efwrite((void *)record_address, record_size, 1, wfoutptr);
  290.         }
  291.     }
  292.  
  293.     /* update memory amounts */
  294.     sublist->memory = next_address;
  295.     sublist->pcount += i;
  296.     sublist->count -= i;
  297.  
  298.     return;
  299. }
  300. /*********************************************************************
  301. sublist_read - get a record from a sublist written to disk
  302. **********************************************************************/
  303. RECORD *
  304. sublist_read(sublist)
  305. SUBLIST *sublist;
  306. {
  307.     static FILE_SIZE disk_address;
  308.     static int eob = 1;
  309.     RECORD *record_address;
  310.     size_t record_size;
  311.  
  312.     /* if there are more records in the work file block */
  313.     if(eob){
  314.         /* get the next block */
  315.         assert(sublist);
  316.         disk_address = sublist->disk;
  317.  
  318.         /* if nothing on disk */
  319.         if(disk_address == EOF){
  320.             /* we're done */
  321.             return (RECORD *)NULL;
  322.         }
  323.  
  324.         /* otherwise update pointer to next block */
  325.         assert(-1L != fseek(wfinptr, disk_address, SEEK_SET));
  326.         efread(&(sublist->disk), sizeof(FILE_SIZE), 1, wfinptr);
  327.  
  328.     }
  329.  
  330.     /* get record size */
  331.     efread(&record_size, sizeof(record_size), 1, wfinptr);
  332.  
  333.     /* get memory space for record, link, and terminating NULL */
  334.     record_address =
  335.         (RECORD *)need(d_stack, 1 + record_size + sizeof(ADDRESS));
  336.  
  337.     /* build record in memory */
  338.      record_address = (RECORD *)mklinks(record_address, 1);
  339.     record_address->field[0] = record_size;
  340.     efread(
  341.         &record_address->field[1],
  342.         record_size - sizeof(int /*record_address->field[0]*/) + 1,
  343.         1,
  344.         wfinptr
  345.     );
  346.     eob = rec_eob(record_address);
  347.     rec_memflag(record_address) = FALSE;
  348.  
  349.     /* and return its address */
  350.     return record_address;
  351. }
  352. /*********************************************************************
  353. sublist_windup - close working file
  354. **********************************************************************/
  355. private
  356. void
  357. sublist_windup(){
  358.     if(wfinptr != (FILE *)NULL)
  359.         /* throw it away */
  360.         fclose(wfinptr);
  361.     if(wfoutptr != (FILE *)NULL){
  362.         /* throw it away */
  363.         fclose(wfoutptr);
  364.         remove(wfname);
  365.     }
  366. }
  367. /*********************************************************************
  368. sublist_input - get next record from sublist
  369. **********************************************************************/
  370. RECORD *
  371. sublist_input(sublist)
  372. SUBLIST *sublist;
  373. {
  374.     RECORD *record_address;
  375.  
  376.     /* if there are records in memory */
  377.     record_address = sublist->memory;
  378.     if(record_address != (RECORD *)NULL){
  379.         /* adjust pointer to sublist in memory */
  380.         assert(sublist);
  381.         sublist->memory =
  382.             (RECORD *)nxtelem(record_address, 0);
  383.         /* and return the first record in the list */
  384.         return record_address;
  385.     }
  386.     else
  387.         return sublist_read(sublist);
  388. }
  389. /*********************************************************************
  390. sublist_output - write records in a sublist i to standard output
  391. **********************************************************************/
  392. void
  393. sublist_output(sublist, uflag)
  394. SUBLIST    *sublist;    /* pointer to sublist to be written */
  395. BOOLEAN uflag;        /* flag to suppress duplicate records */
  396. {
  397.     RECORD *record_address;    /*temporary address */
  398.     BOOLEAN output_flag;
  399.  
  400.     /* get next record from list */
  401.     output_flag = TRUE;
  402.     while(record_address = sublist_input(sublist)){
  403.  
  404.         assert(record_address);
  405.  
  406.         if(output_flag)
  407.             /* write record */
  408.             rec_output(record_address);
  409.  
  410.         output_flag = !uflag;
  411.     }
  412. }
  413.  
  414.